#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""

    注意前提条件: A[0] < a[1], a[n-2] > a[n-1]
"""


class Solution:
    '''
    NOTE: 题目保证了相邻元素都不同!
    '''

    def findPeak(self, A):
        # 保证每次循环: 除start和end外, 之间一定有别的peak
        start, end = 0, len(A) - 1
        assert len(A) >= 3

        while end - start > 3:
            mid = (start + end) // 2

            if A[mid] < A[mid-1]:
                end = mid
                continue
            elif A[mid] < A[mid+1]:
                start = mid
                continue
            else:
                return mid



        # 处理特殊
        if end - start == 2:
            return start + 1

        # 处理特殊
        if end - start == 3:
            if A[start+1] > A[start+2]:
                return start+1
            else:
                return start+2

        assert False
        # find in A[start:end]
        # return start + 1


def main():
    print("start main")

    s = Solution()
    ret = s.findPeak([1, 2, 1, 3, 4, 5, 7, 6])
    print(ret)

if __name__ == "__main__":
    main()
